package club.xiaojiawei.binarytree;

import java.util.LinkedList;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/12/22 11:30 PM
 * @question 226. 翻转二叉树
 * @description 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
 */
public class InvertTree226 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        TreeNode left = new TreeNode(2);
        TreeNode right = new TreeNode(7);
        left.left = new TreeNode(1);
        left.right = new TreeNode(3);
        right.left = new TreeNode(6);
        right.right = new TreeNode(9);
        root.left = left;
        root.right = right;
        TreeNode result = invertTree2(root);
        System.out.println(result);
    }

    /**
     * BFS+队列
     * @param root
     * @return
     */
    public static TreeNode invertTree(TreeNode root) {
        if (root == null){
            return null;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int size;
        TreeNode temp;
        while ((size = queue.size()) > 0){
            for (int i = 0; i < size; i++) {
                TreeNode current = queue.pop();
                if ((temp = current.left) != null){
                    queue.add(current.left);
                }
                if (current.right != null){
                    queue.add(current.right);
                }
                current.left = current.right;
                current.right = temp;
            }
        }
        return root;
    }

    /**
     * DFS+递归
     * @param root
     * @return
     */
    public static TreeNode invertTree2(TreeNode root) {
        if (root == null){
            return null;
        }
        TreeNode temp = root.left;
        invertTree(root.left = root.right);
        invertTree(root.right = temp);
        return root;
    }

    static class TreeNode{

        private int val;

        private TreeNode left;

        private TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }

        public TreeNode getLeft() {
            return left;
        }

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public TreeNode getRight() {
            return right;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }
    }
}
